#pragma once
#include <iostream>
#include <vector>
#include <assert.h>
#include <algorithm>

using std::cout;
using std::endl;

namespace real
{
    inline unsigned long __stl_next_prime(unsigned long n)
	{
		// Note: assumes long is at least 32 bits.
		static const int __stl_num_primes = 28;
		static const unsigned long __stl_prime_list[__stl_num_primes] = {
			53, 97, 193, 389, 769,
			1543, 3079, 6151, 12289, 24593,
			49157, 98317, 196613, 393241, 786433,
			1572869, 3145739, 6291469, 12582917, 25165843,
			50331653, 100663319, 201326611, 402653189, 805306457,
			1610612741, 3221225473, 4294967291
		};
		const unsigned long* first = __stl_prime_list;
		const unsigned long* last = __stl_prime_list + __stl_num_primes;
		const unsigned long* pos = std::lower_bound(first, last, n);
		return pos == last ? *(last - 1) : *pos;
	}
    
    namespace hashtable_open  // 开放式(内耗式)散布模式
    {
        enum State
        {
            EXIST,
            DELETE,
            EMPTY
        };

        template <class K, class V>
        struct HashData
        {
            State _state = EMPTY;
            std::pair<K, V> _kv;
        };

        template<class T>
        struct HashFunc
        {
            size_t operator()(const T& t)
            {
                return size_t(t);
            }
        };

        template <class K, class V, class Hash=HashFunc<K>>
        class HashTable
        {
        private:
            size_t _n ;
            std::vector<HashData<K,V>> _tables;
        public:
            HashTable()
                :_n(0)
                ,_tables(__stl_next_prime(0))
            {}

            HashData<K,V>* Find(const K& key)
            {
                Hash hash;
                size_t hash0 = hash(key)%size_t(_tables.size());
                size_t i = 1;
                size_t hashi = hash0;
                while(_tables[hashi]._state != EMPTY)
                {
                    if(_tables[hashi]._state == EXIST && 
                        _tables[hashi]._kv.first == key)
                        return &(_tables[hashi]);
                    hashi = (hash0+i++)%_tables.size();
                }
                return nullptr;
            }

            bool Insert(const std::pair<K, V>& kv)
            {
                if(Find(kv.first))
                    return false;

                if(_n*10/_tables.size()>=7)
                {
                    // 扩容逻辑
                    HashTable<K,V,Hash> newtable;
                    newtable._tables.resize(__stl_next_prime(_n+1));
                    for(auto& e: _tables)
                    {
                        if(e._state == EXIST)
                        {
                            newtable.Insert(e._kv);
                        }
                    }
                    _tables.swap(newtable._tables);
                }
                // 插入逻辑
                Hash hash;
                size_t hash0 = hash(kv.first)%size_t(_tables.size());
                size_t i = 1;
                size_t hashi = hash0;
                while(_tables[hashi]._state == EXIST)
                {
                    hashi = (hash0+i++)%_tables.size();
                }
                ++_n;
                _tables[hashi]._kv = kv;
                _tables[hashi]._state = EXIST;
                return true;
            }
        };
    }
    
}